package hot_100;

public class 寻找两个正序数组的中位数 {
    public static void main(String[] args) {

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int s = n + m;
        if ((s & 1) == 1) {
            return getMid(nums1, nums2, (s >> 1) + 1);
        } else {
            return (getMid(nums1, nums2, s >> 1) + getMid(nums1, nums2, (s >> 1) + 1)) >> 1;
        }
    }

    public Integer getMid(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int m = nums2.length;
        int idx1 = 0, idx2 = 0;
        while (true) {
            if (idx1 == n)
                return nums2[idx2 + k - 1];
            if (idx2 == m)
                return nums1[idx1 + k - 1];
            if (k == 1)
                return Math.min(nums1[idx1], nums2[idx2]);
            int need = k >> 1;
            int temp1 = Math.min(idx1 + need, n) - 1;
            int temp2 = Math.min(idx2 + need, n) - 1;
            if (nums1[temp1] <= nums2[temp2]) {
                k -= (temp1 - idx1 + 1);
                idx1 = temp1 + 1;
            } else {
                k -= (temp2 - idx2 + 1);
                idx2 = temp2 + 1;
            }
        }
    }

}
